package com.berchen.查找;

import java.util.Arrays;

/**
 * 斐波那契查找
 * 和二分查找差不多 只是MID的计算方式不同
 * 那么如何计算mid？
 * 为什么？
 *
 * 因为斐波那契数列的 前一个数比后一个数之比无限接近0.618
 * mid=left + fib[fibindex-1]-1   fib[fibindex-1]越小 mid越大
 * 1. 将要查询的数组长度弄成一个斐波那契数列中的数据那么长（最接近原数组长度，其余的用最后一个数补）
 * 2. 第一个mid就是要查询数组（新）的长度的黄金分割点的位置
 * 3. 第二个mid就是 左边或者右边？
 *  左边：value<tempArr[mid]
 *      right=mid-1
 *      fibIndex--
 *  右边：value>tempArr[mid]
 *      left=mid+1
 *      fibIndex+=2
 */
public class FibonacciSearch {
    private static int size=20;
    public static void main(String[] args) {
        int[] arr={1,8,12,50,1000,4000,4589};
        System.out.println(fibSearch(arr,4000));
    }

    /**
     *
     * @param arr   需要查询的数组
     * @param value 需要查询的数据值
     * @return
     */
    public static int fibSearch(int[] arr,int value){

        int left=0;
        int right=arr.length-1;
        int fibIndex=0; // 表示斐波那契分割数值的下标
        int mid=0;
        int[] fibArr=fib();   // 获取斐波那契数列
        System.out.println(Arrays.toString(fibArr));

        // 获取到斐波那契分割数值的下标
        // 为什么要获取斐波那契分割值的下标？？？
        while (right>fibArr[fibIndex]-1){
            fibIndex++;
        }
        // 因为fibArr[fibIndex]的值 可能大于arr的值，因此我们需要使用Arrays类，构造一个新的数组，并指向arr[]
        // 不足的部分会使用0来填充
        int[] temp= Arrays.copyOf(arr,fibArr[fibIndex]);
        // 使用arr[]数组最后一个数来填充temp
        // temp=[1,4,6,8,10]=>[1,4,6,8,10,10,10,10,10]
        for(int i =right+1;i<temp.length;i++){
            temp[i]=arr[right];
        }
        // 使用while来处理，找到我们需要找的value
        while (left<=right){

            mid=left+fibArr[fibIndex-1]-1;
            if(value<temp[mid]){    // 我们应该继续向数组的前面查找（左边）
                right=mid-1;
                // 为什么是fibIndex--
                // 说明
                // 1. 全部元素=前面的元素+后面元素
                // 2. fibArr[fibIndex]=fibArr[fibIndex-1]+fibArr[fibIndex-2]
                // 因为前面有fibArr[fibIndex-1]个元素，所以可以继续拆分fibArr[fibIndex-1]=fibArr[fibIndex-2]+fibArr[fibIndex-3]
                // 即在fibArr[fibIndex-1]的前面继续查找fibIndex--
                // 即在下次循环mid=fibArr[fibIndex-1-1]-1
                fibIndex--;
            }
            else if(value>temp[mid]){// 我们应该继续向数组的后面查找（右边）
                left=mid+1;
                // 为什么是fidIndex-=2
                // 1. 全部元素=前面的元素+后面的元素
                // 2. fibArr[fibIndex]=fibArr[fibIndex-1]+fibArr[fibIndex-2]
                // 3. 因为后面我们还有fibArr[fibIndex-2] 所以可以继续拆分fibArr[fibIndex-1]=fibArr[fibIndex-3]+fibArr[fibIndex-4]
                // 4. 即在fibArr[fibIndex-2]的前面进行查找 fibIndex-=2
                // 5. 即下次循环mid=fibArr[fibIndex-1-2]-1
                fibIndex-=2;
            }
            else {
                // 需要确定，返回的是那个下标
                if(mid<=right){
                    return mid;
                }
                else {
                    return right;
                }
            }
        }
        return -1;
    }

    /**
     * 创建一个斐波那契数列
     * @return
     */
    public static int[] fib(){
        int[] f=new int[size];
        f[0]=1;
        f[1]=1;
        for(int i =2;i<size;i++){
            f[i]=f[i-1]+f[i-2];
        }
        return f;
    }
}
